package com.zang.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 全排列
 * @author ZVerify
 * @since 2022/11/15 21:07
 * @see <a href="https://leetcode.cn/problems/permutations/">...</a>
 **/
public class 全排列 {
    public static void main(String[] args) {
        全排列 a = new 全排列();
        a.permute(new int[]{1,2,3});
    }
    List<List<Integer>> result = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    boolean[] set = null;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) return null;
        set = new boolean[nums.length];
        backtrack(nums);
        return result;
    }

    private void backtrack(int[] nums) {
        if (list.size() == nums.length) result.add(new ArrayList<>(list));

        for (int i = 0; i < nums.length; i++) {
            if (set[i]) continue;
            set[i] = true;
            list.add(nums[i]);
            backtrack(nums);
            set[i] = false;
            list.remove(list.size() - 1);
        }
    }
}
